1   // Fig. 15.3: listnd.h
2   // ListNode template definition
3   #ifndef LISTND_H
4   #define LISTND_H
5   
6   template< class NODETYPE > class List;  // forward declaration
7   
8   template<class NODETYPE>
9   class ListNode {
10     friend class List< NODETYPE >; // make List a friend
11  public:
12     ListNode( const NODETYPE & );  // constructor
13     NODETYPE getData() const;      // return data in the node
14  private:
15     NODETYPE data;                 // data
16     ListNode< NODETYPE > *nextPtr; // next node in the list
17  };
18  
19  // Constructor
20  template<class NODETYPE>
21  ListNode< NODETYPE >::ListNode( const NODETYPE &info )
22     : data( info ), nextPtr( 0 ) { }
23  
24  // Return a copy of the data in the node
25  template< class NODETYPE >
26  NODETYPE ListNode< NODETYPE >::getData() const { return data; }
27  
28  #endif
29  
30  
31  // Fig. 15.3: list.h
32  // Template List class definition
33  #ifndef LIST_H
34  #define LIST_H
35  
36  #include <iostream.h>
37  #include <assert.h>
38  #include "listnd.h"
39  
40  template< class NODETYPE >
41  class List {
42  public:
43     List();      // constructor
44     ~List();     // destructor
45     void insertAtFront( const NODETYPE & );
46     void insertAtBack( const NODETYPE & );
47     bool removeFromFront( NODETYPE & );
48     bool removeFromBack( NODETYPE & );
49     bool isEmpty() const;
50     void print() const;
51  private:
52     ListNode< NODETYPE > *firstPtr;  // pointer to first node
53     ListNode< NODETYPE > *lastPtr;   // pointer to last node
54  
55     // Utility function to allocate a new node
56     ListNode< NODETYPE > *getNewNode( const NODETYPE & );
57  };
58  
59  // Default constructor
60  template< class NODETYPE >
61  List< NODETYPE >::List() : firstPtr( 0 ), lastPtr( 0 ) { }
62  
63  // Destructor
64  template< class NODETYPE >
65  List< NODETYPE >::~List()
66  {
67     if ( !isEmpty() ) {    // List is not empty
68        cout << "Destroying nodes ...\n";
69  
70        ListNode< NODETYPE > *currentPtr = firstPtr, *tempPtr;
71  
72        while ( currentPtr != 0 ) {  // delete remaining nodes
73           tempPtr = currentPtr;
74           cout << tempPtr->data << '\n';
75           currentPtr = currentPtr->nextPtr;
76           delete tempPtr;
77        }
78     }
79  
80     cout << "All nodes destroyed\n\n";
81  }
82  
83  // Insert a node at the front of the list
84  template< class NODETYPE >
85  void List< NODETYPE >::insertAtFront( const NODETYPE &value )
86  {
87     ListNode< NODETYPE > *newPtr = getNewNode( value );
88  
89     if ( isEmpty() )  // List is empty
90        firstPtr = lastPtr = newPtr;
91     else {          // List is not empty
92        newPtr->nextPtr = firstPtr;
93        firstPtr = newPtr;
94     }
95  }
96  
97  // Insert a node at the back of the list
98  template< class NODETYPE >
99  void List< NODETYPE >::insertAtBack( const NODETYPE &value )
100 {
101    ListNode< NODETYPE > *newPtr = getNewNode( value );
102 
103    if ( isEmpty() )  // List is empty
104       firstPtr = lastPtr = newPtr;
105    else {          // List is not empty
106       lastPtr->nextPtr = newPtr;
107       lastPtr = newPtr;
108    }
109 }
110 
111 // Delete a node from the front of the list
112 template< class NODETYPE >
113 bool List< NODETYPE >::removeFromFront( NODETYPE &value )
114 {
115    if ( isEmpty() )             // List is empty
116       return false;             // delete unsuccessful
117    else {
118       ListNode< NODETYPE > *tempPtr = firstPtr;
119 
120       if ( firstPtr == lastPtr )
121          firstPtr = lastPtr = 0;
122       else
123          firstPtr = firstPtr->nextPtr;
124 
125       value = tempPtr->data;  // data being removed
126       delete tempPtr;
127       return true;            // delete successful
128    }
129 }
130 
131 // Delete a node from the back of the list
132 template< class NODETYPE >
133 bool List< NODETYPE >::removeFromBack( NODETYPE &value )
134 {
135    if ( isEmpty() )
136       return false;   // delete unsuccessful
137    else {
138       ListNode< NODETYPE > *tempPtr = lastPtr;
139 
140       if ( firstPtr == lastPtr )
141          firstPtr = lastPtr = 0;
142       else {
143          ListNode< NODETYPE > *currentPtr = firstPtr;
144 
145          while ( currentPtr->nextPtr != lastPtr )
146             currentPtr = currentPtr->nextPtr;
147 
148          lastPtr = currentPtr;
149          currentPtr->nextPtr = 0;
150       }
151 
152       value = tempPtr->data;
153       delete tempPtr;
154       return true;   // delete successful
155    }
156 }
157 
158 // Is the List empty?
159 template< class NODETYPE > 
160 bool List< NODETYPE >::isEmpty() const 
161    { return firstPtr == 0; }
162 
163 // Return a pointer to a newly allocated node
164 template< class NODETYPE >
165 ListNode< NODETYPE > *List< NODETYPE >::getNewNode( 
166                                         const NODETYPE &value )
167 {
168    ListNode< NODETYPE > *ptr = 
169       new ListNode< NODETYPE >( value );
170    assert( ptr != 0 );
171    return ptr;
172 }
173 
174 // Display the contents of the List
175 template< class NODETYPE >
176 void List< NODETYPE >::print() const
177 {
178    if ( isEmpty() ) {
179       cout << "The list is empty\n\n";
180       return;
181    }
182 
183    ListNode< NODETYPE > *currentPtr = firstPtr;
184 
185    cout << "The list is: ";
186 
187    while ( currentPtr != 0 ) {
188       cout << currentPtr->data << ' ';
189       currentPtr = currentPtr->nextPtr;
190    }
191 
192    cout << "\n\n";
193 }
194 
195 #endif
196 
197 
198 // Fig. 15.3: fig15_03.cpp
199 // List class test
200 #include <iostream.h>
201 #include "list.h"
202 
203 // Function to test an integer List
204 template< class T >
205 void testList( List< T > &listObject, const char *type )
206 {
207    cout << "Testing a List of " << type << " values\n";
208 
209    instructions();
210    int choice;
211    T value;
212 
213    do {
214       cout << "? ";
215       cin >> choice;
216 
217       switch ( choice ) {
218          case 1:
219             cout << "Enter " << type << ": ";
220             cin >> value;
221             listObject.insertAtFront( value );
222             listObject.print();
223             break;
224          case 2:
225             cout << "Enter " << type << ": ";
226             cin >> value;
227             listObject.insertAtBack( value );
228             listObject.print();
229             break;
230          case 3:
231             if ( listObject.removeFromFront( value ) )
232                cout << value << " removed from list\n";
233 
234             listObject.print();
235             break;
236          case 4:
237             if ( listObject.removeFromBack( value ) )
238                cout << value << " removed from list\n";
239 
240             listObject.print();
241             break;
242       }
243    } while ( choice != 5 );
244 
245    cout << "End list test\n\n";
246 }
247 
248 void instructions()
249 {
250    cout << "Enter one of the following:\n"
251         << "  1 to insert at beginning of list\n" 
252         << "  2 to insert at end of list\n" 
253         << "  3 to delete from beginning of list\n" 
254         << "  4 to delete from end of list\n" 
255         << "  5 to end list processing\n";
256 }
257 
258 int main()
259 {
260    List< int > integerList;
261    testList( integerList, "integer" ); // test integerList
262 
263    List< float > floatList;
264    testList( floatList, "float" );     // test integerList
265 
266    return 0;
267 }